const CellType = require('./CellType');
const Cell = require('./Cell');
const Direction = require('./Direction');
const assert = require('./assert');
const DEBUG = false;

const Grid = function(n, shouldPrint) {
  this.n = n;
  this.shouldPrint = shouldPrint;
  this.grid = [];
  for (let i = 0; i < n + 2; i++) {
    this.grid[i] = [];
  }
  for (let i = 0; i < n + 2; i++) {
    this.grid[i][0] = new Cell(i, 0, CellType.WALL);
    this.grid[i][n + 1] = new Cell(i, 0, CellType.WALL);
  }
  for (let i = 0; i < n + 2; i++) {
    this.grid[0][i] = new Cell(i, 0, CellType.WALL);
    this.grid[n + 1][i] = new Cell(i, 0, CellType.WALL);
  }
  for (let i = 1; i < n + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
      this.grid[i][j] = new Cell(i, j, CellType.PATH);
    }
  }
  this.animals = {};
  this.colors = [];
  for (let i = 0; i < n + 2; i++) {
    this.colors[i] = [];
  }
};

Grid.prototype.toString = function() {
  let string = '';
  for (let i = 0; i < this.n + 2; i++) {
    for (let j = 0; j < this.n + 2; j++) {
      string += this.grid[i][j].toString();
    }
    string += '\n';
  }
  string += '\n';
  return string;
};

Grid.prototype.print = function() {
  console.log(this.toString());
};

Grid.prototype.hasEmptyCell = function() {
  for (let i = 0; i < this.n + 2; i++) {
    for (let j = 0; j < this.n + 2; j++) {
      if (CellType.isPath(this.grid[i][j].type)) {
        return true;
      }
    }
  }
  return false;
};

Grid.prototype.assertCellEmpty = function(y, x) {
  assert(
    this.grid[y][x].type === CellType.PATH,
    'failed at add new cell, the cell [' + y + '][' + x + '] is not empty'
  );
};

Grid.prototype.addAnimal = function(y, x, category, sequence) {
  this.assertCellEmpty(y, x);
  this.grid[y][x] = new Cell(y, x, CellType.ANIMAL);
  this.grid[y][x].animal = {
    category,
    sequence,
  };
  if (!this.animals[category] || this.animals[category] < sequence) {
    this.animals[category] = sequence;
  }
};

Grid.prototype.addWall = function(y, x) {
  this.assertCellEmpty(y, x);
  this.grid[y][x] = new Cell(y, x, CellType.WALL);
};

Grid.prototype.addPathBoth = function(y, x) {
  this.assertCellEmpty(y, x);
  this.grid[y][x] = new Cell(y, x, CellType.PATH_BOTH);
};

Grid.prototype.solve = function() {
  return this.step(1, 1, null, null);
};

Grid.prototype.step = function(y, x, animal, direction) {
  if (DEBUG) {
    this.print();
  }
  if (y === this.n + 1 && animal === null) {
    const result = !this.hasEmptyCell();
    if (result && this.shouldPrint) {
      this.print();
    }
    return result;
  }
  const cell = this.grid[y][x];
  if (animal === null) {
    if (cell.type === CellType.ANIMAL && cell.animal.sequence < this.animals[cell.animal.category] && !this.colors[y][x]) {
      this.colors[y][x] = true;
      const result = this.step(y + 1, x, cell.animal, Direction.DOWN) ||
        this.step(y - 1, x, cell.animal, Direction.UP) ||
        this.step(y, x + 1, cell.animal, Direction.RIGHT) ||
        this.step(y, x - 1, cell.animal, Direction.LEFT);
      this.colors[y][x] = false;
      return result;
    } else {
      return x === this.n ?
        this.step(y + 1, 1, null, null) :
        this.step(y, x + 1, null, null);
    }
  }
  // there is already an animal moving
  if (cell.type === CellType.ANIMAL && cell.animal.category !== animal.category) {
    return false;
  } else if (cell.type === CellType.ANIMAL && cell.animal.sequence !== animal.sequence + 1) {
    return false;
  } else if (cell.type === CellType.ANIMAL) {
    return this.step(1, 1, null, null);
  } else if (cell.type === CellType.WALL) {
    return false;
  } else if (cell.type === CellType.PATH) {
    if (this.pathTrapsAnimal(y, x, animal)) {
      return false;
    }
    cell.type = CellType.ROUTE;
    if (this.hasEmptyArea()) {
      cell.type = CellType.PATH;
      return false;
    }
    cell.route = animal;
    cell.direction = direction;
    const result = this.step(y + 1, x, animal, Direction.DOWN) ||
      this.step(y - 1, x, animal, Direction.UP) ||
      this.step(y, x + 1, animal, Direction.RIGHT) ||
      this.step(y, x - 1, animal, Direction.LEFT);
    cell.type = CellType.PATH;
    cell.direction = null;
    cell.route = null;
    return result;
  } else if (cell.type === CellType.PATH_BOTH && (direction === Direction.RIGHT || direction === Direction.LEFT)) {
    cell.type = CellType.ROUTE_HORIZONTAL;
    cell.routeHorizontal = animal;
    cell.directionHorizontal = direction;
    const result = this.step(y, x + 1, animal, Direction.RIGHT) ||
      this.step(y, x - 1, animal, Direction.LEFT);
    cell.type = CellType.PATH_BOTH;
    cell.routeHorizontal = null;
    cell.directionHorizontal = null;
    return result;
  } else if (cell.type === CellType.PATH_BOTH && (direction === Direction.UP || direction === Direction.DOWN)) {
    cell.type = CellType.ROUTE_VERTICAL;
    cell.routeVertical = animal;
    cell.directionVertical = direction;
    const result = this.step(y + 1, x, animal, Direction.DOWN) ||
      this.step(y - 1, x, animal, Direction.UP);
    cell.type = CellType.PATH_BOTH;
    cell.routeVertical = null;
    cell.directionVertical = null;
    return result;
  } else if (cell.type === CellType.ROUTE) {
    return false;
  } else if (cell.type === CellType.ROUTE_HORIZONTAL && (direction === Direction.RIGHT || direction === Direction.LEFT)) {
    return false;
  } else if (cell.type === CellType.ROUTE_HORIZONTAL && (direction === Direction.DOWN || direction === Direction.UP)) {
    cell.type = CellType.ROUTE_BOTH;
    cell.routeVertical = animal;
    cell.directionVertical = direction;
    const result = this.step(y + 1, x, animal, Direction.DOWN) ||
      this.step(y - 1, x, animal, Direction.UP);
    cell.type = CellType.ROUTE_HORIZONTAL;
    cell.routeVertical = null;
    cell.directionVertical = null;
    return result;
  } else if (cell.type === CellType.ROUTE_VERTICAL && (direction === Direction.RIGHT || direction === Direction.LEFT)) {
    cell.type = CellType.ROUTE_BOTH;
    cell.routeHorizontal = animal;
    cell.directionHorizontal = direction;
    const result = this.step(y, x + 1, animal, Direction.RIGHT) ||
      this.step(y, x - 1, animal, Direction.LEFT);
    cell.type = CellType.ROUTE_VERTICAL;
    cell.directionHorizontal = null;
    cell.routeHorizontal = null;
    return result;
  } else if (cell.type === CellType.ROUTE_VERTICAL && (direction === Direction.DOWN || direction === Direction.UP)) {
    return false;
  } else if (cell.type === CellType.ROUTE_BOTH) {
    return false;
  }
  assert(false, 'should not reach here: ' + y + ' ' + x + ' ' + cell + ' ' + animal.category + ' ' + animal.sequence + ' ' + direction);
};

Grid.prototype.pathTrapsAnimal = function(y, x, animal) {
  const cell = this.grid[y][x];
  cell.type = CellType.ROUTE;
  const result = this.isAnimalTrapped(y - 1, x, animal) ||
    this.isAnimalTrapped(y + 1, x, animal) ||
    this.isAnimalTrapped(y, x - 1, animal) ||
    this.isAnimalTrapped(y, x + 1, animal);
  cell.type = CellType.PATH;
  return result;
};

Grid.prototype.isAnimalTrapped = function(y, x, animal) {
  const cell = this.grid[y][x];
  if (cell.type !== CellType.ANIMAL) {
    return false;
  }
  if (cell.animal.category === animal.category && cell.animal.sequence === animal.sequence + 1) {
    return false;
  }
  if (cell.animal.sequence === this.animals[cell.animal.category]) {
    return false;
  }
  if (this.colors[y][x]) {
    return false;
  }
  const blockUp = CellType.isBlock(this.grid[y - 1][x]) ||
    this.grid[y - 1][x].type === CellType.ROUTE_VERTICAL ||
    (this.grid[y - 1][x].type === CellType.ANIMAL && this.grid[y - 1][x].category !== cell.animal.category);
  const blockDown = CellType.isBlock(this.grid[y + 1][x]) ||
    this.grid[y + 1][x].type === CellType.ROUTE_VERTICAL ||
    (this.grid[y + 1][x].type === CellType.ANIMAL && this.grid[y + 1][x].category !== cell.animal.category);
  const blockLeft = CellType.isBlock(this.grid[y][x - 1]) ||
    this.grid[y][x - 1].type === CellType.ROUTE_HORIZONTAL ||
    (this.grid[y][x - 1].type === CellType.ANIMAL && this.grid[y][x - 1].category !== cell.animal.category);
  const blockRight = CellType.isBlock(this.grid[y][x + 1]) ||
    this.grid[y][x + 1].type === CellType.ROUTE_HORIZONTAL ||
    (this.grid[y][x + 1].type === CellType.ANIMAL && this.grid[y][x + 1].category !== cell.animal.category);
  return (blockUp && blockDown && blockLeft && blockRight);
};

Grid.prototype.hasEmptyArea = function() {
  const step = function(y, x, area) {
    const cell = this.grid[y][x];
    if (CellType.isBlock(cell.type)) {
      return true;
    }
    if (area[y][x]) {
      return true;
    }
    if (cell.type === CellType.ANIMAL) {
      return false;
    }
    area[y][x] = true;
    return step.call(this, y + 1, x, area) &&
      step.call(this, y - 1, x, area) &&
      step.call(this, y, x + 1, area) &&
      step.call(this, y, x - 1, area);
  };
  const isEmptyArea = function(y, x) {
    if (CellType.isBlock(this.grid[y][x].type) ||
      this.grid[y][x].type === CellType.ANIMAL) {
      return false;
    };
    const area = [];
    for (let i = 0; i < this.n + 2; i++) {
      area[i] = [];
      for (let j = 0; j < this.n + 2; j++) {
        area[i][j] = false;
      }
    }
    return step.call(this, y, x, area);
  };
  for (let i = 1; i < this.n + 1; i++) {
    for (let j = 1; j < this.n + 1; j++) {
      if (isEmptyArea.call(this, i, j)) {
        return true;
      }
    }
  }
};

module.exports = Grid;
